package com.ca.singlesignon.ConsistentHash;

import java.nio.ByteBuffer;
import java.nio.ByteOrder;
import java.util.Collection;
import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentHash<T> {

    /**
     * 哈希函数
     */
    private final HashFunction hashFunction;
    /**
     * 虚拟节点数
     */
    private final int numberOfReplicas;
    /**
     * hash环形空间
     */
    private final SortedMap<Integer,T> circle=new TreeMap<Integer,T>();

    public ConsistentHash(HashFunction hashFunction,int numberOfReplicas,Collection<T> nodes) {
        this.hashFunction = hashFunction;
        this.numberOfReplicas=numberOfReplicas;
        for(T node:nodes){
            addNode(node);
        }
    }

    /**
     * 添加一个物理节点，就产生numberOfReplicas 个虚拟节点
     * @param node
     */
    public void addNode(T node){
        for(int i=0;i<numberOfReplicas;i++){
            int hashvalue=hashFunction.hash(node.toString()+i);
            circle.put(hashvalue,node);
        }
    }

    /**
     * 移除一个物理节点，就移除numberOfReplicas 个虚拟节点
     * @param node
     */
    public void removeNode(T node){
        for(int i=0;i<numberOfReplicas;i++){
            int hashvalue=hashFunction.hash(node.toString()+i);
            circle.remove(hashvalue,node);
        }
    }

    public T getNode(Object key){
        if(circle.isEmpty()){
            return null;
        }
        int hashValue=hashFunction.hash(key);
        //如果保存一个Object对象，映射的hash值不存在，就沿着circle寻找写一个虚拟节点
        if(!circle.containsKey(hashValue)){
            // 返回键大于或等于hash的node，即沿环的顺时针找到一个虚拟节点
            SortedMap<Integer,T> tailMap=circle.tailMap(hashValue);
            hashValue=tailMap.isEmpty()?circle.firstKey():tailMap.firstKey();
        }
        return circle.get(hashValue);
    }


    static class HashFunction {
        /**
         * MurMurHash算法，是非加密HASH算法，性能很高，
         * 比传统的CRC32,MD5，SHA-1（这两个算法都是加密HASH算法，复杂度本身就很高，带来的性能上的损害也不可避免）
         * 等HASH算法要快很多，而且据说这个算法的碰撞率很低. http://murmurhash.googlepages.com/
         */
        int hash(Object key) {
            ByteBuffer buf = ByteBuffer.wrap(key.toString().getBytes());
            int seed = 0x1234ABCD;

            ByteOrder byteOrder = buf.order();
            buf.order(ByteOrder.LITTLE_ENDIAN);

            long m = 0xc6a4a7935bd1e995L;
            int r = 47;

            long h = seed ^ (buf.remaining() * m);

            long k;
            while (buf.remaining() >= 8) {
                k = buf.getLong();

                k *= m;
                k ^= k >>> r;
                k *= m;

                h ^= k;
                h *= m;
            }

            if (buf.remaining() > 0) {
                ByteBuffer finish = ByteBuffer.allocate(8).order(
                        ByteOrder.LITTLE_ENDIAN);
                finish.put(buf).rewind();
                h ^= finish.getLong();
                h *= m;
            }

            h ^= h >>> r;
            h *= m;
            h ^= h >>> r;
            buf.order(byteOrder);
            return (int) h;
        }
    }

}
